"""
1. 创建四个指针，odd奇数指针，奇数头节点oddhead;even偶数指针，偶数头节点evenhead
2.  odd.next = even.next
    odd = even.next
    even.next = odd.next
    even = odd.next
3. 将奇数指针连到偶数头部

"""


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# class Solution:
#     def oddEvenList(self, head: ListNode) -> ListNode:
#         if not head:
#             return head
#
#         # 奇数
#         odd = head
#         oddhead = head
#         # 偶数
#         even = head.next
#         evenhead = head.next
#
#         while even and even.next:
#             # 更改连接
#             odd.next = even.next
#             odd = even.next
#             even.next = odd.next
#             even = odd.next
#
#         # 连接两个断开的链表
#         odd.next = evenhead
#         return head


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 1. 特殊情况：链表长度不足2
        if not head or not head.next:
            return head

        # 2. 初始化五个指针odd, oddhead, even, evenhead, cur
        odd, oddhead = head, head
        even, evenhead = head.next, head.next

        # 3. 算法流程先连接奇偶链表
        while True:
            if not odd.next or not even.next:
                odd.next = evenhead
                even.next = None
                return oddhead
            if even.next:
                odd.next = even.next
                odd = even.next
            if odd.next:
                even.next = odd.next
                even = odd.next

######################################
"""
特殊情况：链表长度不足3，直接返回head
head is None or head.next is None

首先，初始化三个指针p1,p2,cur指向第一结点、第二结点、第三结点，初始化index=3表示第三结点的位置，初始化even_head指向head.next表示偶数节点的头部

然后，如果index & 1 == 1表示为当前结点Cur奇数结点，则连接前一个和当前奇数节点p1.next = cur，更新前一个奇数结点指针p1 = cur，更新当前结点与索引cur = cur.next,index+=1
    如果index & 1 == 0表示当前结点cur偶数结点，则连接前一个和当前偶数结点p2.next = cur，更新前一个偶数结点指针p2=cur，更新当前节点与索引cur = cur.next,index+=1
    如果当前节点变为空指针，连接前一个奇数结点和偶数结点的头结点
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None or head.next.next is None:
            return head
        
        p1, p2, cur = head, head.next, head.next.next
        index = 3
        odd_head, even_head = head, head.next

        while True:
            if index & 1 == 1:
                p1.next = cur
                p1 = cur

                cur = cur.next
                index += 1
            else:
                p2.next = cur
                p2 = cur

                cur = cur.next
                index += 1
            
            if cur is None:
                p1.next = even_head
                p2.next = None  # 其实这一步可有可无
                return odd_head